package com.Q08;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @version v1.0.0
 * 创建时间：2022/8/5 17:11
 */
public class Q08_12 {
    // EightQueen
    List<List<String>> res;
    public List<List<String>> solveNQueens(int n) {
        res = new ArrayList<>();
        if (n==1){
            ArrayList<String> strings = new ArrayList<>();
            strings.add("Q");
            res.add(strings);
            return res;
        }
        if (n<=3) return res;
        int[][] grid = new int[n][n];
        help(0,grid,new ArrayList<String>());
        return res;
    }

    private void help(int curRow,int[][] grid,List<String> solution){
        if(curRow == grid.length){
            res.add(new ArrayList<>(solution));
            return;
        }
        for(int c = 0;c<grid.length;c++){
            if(checkSettle(grid,curRow,c)){
                grid[curRow][c] = 1;
                // 一行n个元素都填上.  第j个元素填上Q  然后add
                char[] rowChars = new char[grid.length];
                Arrays.fill(rowChars,'.');
                rowChars[c] = 'Q';
                solution.add(String.valueOf(rowChars));
                help(curRow+1,grid,solution);
                solution.remove(solution.size()-1);
                grid[curRow][c] = 0;
            }
        }
    }

    private boolean checkSettle(int[][] grid,int row,int col){
        for (int i = 0; i < row; i++) { // 这是一个剪枝
            if (grid[i][col] == 1) {
                return false;
            }
        }
        // 检查 45度角是否有皇后
        for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {
            if (grid[i][j] == 1) {
                return false;
            }
        }
        // 检查 135度角是否有皇后
        for(int i = row - 1, j = col + 1; i >= 0 && j < grid.length; i--, j++) {
            if (grid[i][j] == 1) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Q08_12 q08_12 = new Q08_12();
        List<List<String>> lists = q08_12.solveNQueens(4);
        lists.forEach(p->{
            p.forEach(in -> System.out.println(in));
            System.out.println("---------");
        });

    }
}
